package com.lun.swordtowardoffer2.c03;

import java.util.ArrayList;
import java.util.List;

public class FindAnagrams {

	public List<Integer> findAnagrams(String s1, String s2){
		List<Integer> result = new ArrayList<>();
		if(s1.length() < s2.length()) return result; 
		
		int[] counts = new int[26];
		
		for(int i = 0; i < s2.length(); i++) {
			counts[s2.charAt(i) - 'a']++;
			counts[s1.charAt(i) - 'a']--;
		}
		
		if(areAllZero(counts)) result.add(0);
		
		for(int i = s2.length(); i < s1.length(); i++) {
			counts[s1.charAt(i)-'a']--;
			counts[s1.charAt(i - s2.length())-'a']++;
			
			if(areAllZero(counts)) result.add(i - s2.length() + 1);
		}
		return result;
	}
	
	private boolean areAllZero(int[] counts) {
		for(int count : counts) {
			if(count != 0)
				return false;
		}
		return true;
	}
}
